enum RB_COLOR {
    RED,
    BLACK,
};

template<typename K, typename V>
class RBNode {
public:
    RBNode()  {
        m_color = RED; 
        m_left = nullptr; 
        m_right = nullptr; 
        m_parent = nullptr;
    }

    explicit RBNode(K key, V val): 
        m_key(key), m_value(val), m_color(RED),
        m_left(nullptr), m_right(nullptr), m_parent(nullptr) {}

    ~RBNode() {}

    inline K get_key() {
        return m_key;
    }

    inline void set_color(RB_COLOR c) {
        m_color = c;
    }

    inline RBNode<K, V>* left() {
        return m_left;
    }

    inline RBNode<K, V>* right() {
        return m_right;
    }

    inline RBNode<K, V>* parent() {
        return m_parent;
    }

    inline void set_parent(RBNode<K, V>* p) {
        m_parent = p;
    }

    inline void set_left(RBNode<K, V>* l) {
        m_left = l;
    }

    inline void set_right(RBNode<K, V>* r) {
        m_right = r;
    }

    inline bool is_less(RBNode<K, V>* other) {
        return m_key < other->get_key();
    }

private:
    K m_key;
    V m_value;

    char m_color;
    RBNode<K, V> *m_parent;
    RBNode<K, V> *m_left;
    RBNode<K, V> *m_right;
};

template<typename K, typename V>
class RBTree {
public:
    RBTree() {
        //m_nil = new RBNode<K, V>();
        //m_nil->set_color(BLACK);
        m_root = nullptr;
    }
    ~RBTree() {}

    void insert(K key, V val) { 
        RBNode<K, V>* node = new RBNode<K, V>(key, val);
        assert(nullptr != node);
        RBNode<K, V>* p = m_root;
        while (nullptr != p) {
            if (node->is_less(p)) {
                auto l = p->left();
                if (nullptr == l) {
                    break;
                } else {
                    p = l;
                }
            } else {
                auto r = p->left();
                if (nullptr == r) {
                    break;
                } else {
                    p = r;
                }
            }
        }
        if (p == nullptr) {
            m_root = node;
            m_root->set_color(BLACK);
            return;
        } else if (node->is_less(p)) {
            p->set_left(node);
        } else {
            p->set_right(node);
        }

        fix_after_insert(node);
    }
    bool erase(K key) { return false; }
private:

    void transplate(RBNode<K, V> *ori, RBNode<K, V> *after) {

    }
    void fix_after_insert(RBNode<K, V> *n) {

    }
    void fix_after_delete();
private:
    RBNode<K, V> *m_root;
    //RBNode<K, V> *m_nil;
};